﻿
#include <iostream>
#include <string>
using namespace std;
const int N = 26;		//

struct trieNode{	//字典树节点的结构体
	char val;		//节点值
	trieNode** son;		//二级指针
	int cnt;		//用于标记
	trieNode(char c) {		//初始化
		val = c;
		son = new trieNode*[N];
		for (int i = 0; i < N; i++) son[i] = 0;
		cnt = 0;
	}
};

trieNode * root;		//创建根节点

void insert(string s)		//插入方法，参数为输入的字符串
{
	trieNode* p = root;		//创建结构体指针p，指向root
	for (int i = 0; i < s.length(); i++) {	
		int c = s[i] - 'a';
		if (!p->son[c])		//假如节点的son指向的trieNode类型的表中的第c个元素为空
			p->son[c]= new trieNode(c);	//在节点的son指向的trieNode类型的表中的第c个元素创建一个新节点，c作为新节点的初始化参数
		p = p->son[c];		//指针p移动指向新节点
	}
	p->cnt++;	//改标记值，表示有单词
}
int query(string s)		//查询方法
{
	trieNode* p = root;		//trieNode类型的指针p
	for (int i = 0; i < s.length(); i++) {
		int c = s[i] - 'a';		//c作为查找的线索
		if (!p->son[c])return 0;	//如果指向的为空则返回0；
		p = p->son[c];		//如果存在，则指向下一个节点
	}
	return p->cnt;		//返回标记值；
}
/*bool delete_trie(string s)
{
	trieNode* p = root;
	int i = 0;
	if(delete_node(root,i,s))	return 1;	//删除完毕返回真
	return 0;			//否则返回假
}*/
bool delete_node(trieNode* p,int i,string s)	//删除单词,p指针指向节点，s是要删除的字符串，i是字符串中的字符序号
{
	if (i == s.length())	//边界条件
	{
		if (p->cnt > 0)		//如果标识大于0，则令标识为0，从标识符上来看表示已经删除该节点
			p->cnt=0;
		return 1;		//到达边界 返回真
	}
	int j = s[i] - 'a';		//j是子节点数组中的下标
	i++;				//i向后移
	if (!delete_node(p->son[j], i, s))		//递归，如果返回值为假就执行
		return 0;
	int sum = 0;	//sum用来计数
	for (int a = 0; a < N; a++)		//查看p指针指向的节点是否有多个子节点
	{
		if (p->son[a])	sum++;
	}
	if (sum >1||p->son[j]->son)		//如果有多个子节点，则不能删除，或者子节点后面还有子节点，也不能删除
		return 0;		
	delete p->son[j];		//释放子节点内存
	p->son[j] = nullptr;	//指针指向空
	return 1;		//删除成功
}
int main()
{
	root = new trieNode(' ');	//root节点初始化；
	int in = 10;
	string s;
	while (in) {
		cout << "请输入数字进行操作：1.插入；2.查询；3.删除;4.退出" << endl;
		cin >> in;
		switch (in)
		{
		case 1: {
			cout << "请输入：" << endl;
			cin >> s;
			insert(s);
			cout << s << "插入成功" << endl;
			break; }
		case 2: {
			cout << "请输入：" << endl;
			cin >> s;
			if (query(s))
				cout << s << "在字典树中查询到" << endl;
			else
				cout << s << "未查找到" << endl;
			break;
		}
		case 3: {
			cout << "请输入：" << endl;
			cin >> s;
			delete_node(root, 0, s);
				cout << s << "删除成功" << endl;
			break;
		}
		case 4:return 0;
		default: {
			cout << "输入错误！请重新输入" << endl;
			}
			break;
		}
	}
	return 0;
}

